package org.groupg.practice;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.traverse.TopologicalOrderIterator;

import java.util.HashSet;
import java.util.Set;

public class DAGTraversal {
    public static void main(String[] args) {
        // 创建一个有向图
        Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

        // 添加节点
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("C01");
        graph.addVertex("C02");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F"); // 添加一个无度的节点作为示例

        // 添加边
        graph.addEdge("A", "B");
        graph.addEdge("B", "C");
        graph.addEdge("B", "C01");
        graph.addEdge("B", "C02");
        graph.addEdge("C", "D");
        graph.addEdge("A", "D");
        graph.addEdge("C01", "D");
        graph.addEdge("D", "E");
        graph.addEdge("E", "C02");

        // 遍历无度的节点（既没有入度也没有出度的节点）
        System.out.println("无度节点");
        for (String vertex : graph.vertexSet()) {
            if (graph.inDegreeOf(vertex) == 0 && graph.outDegreeOf(vertex) == 0) {
                System.out.println(vertex);
            }
        }

        // 从源节点开始遍历到汇点，仅输出有度节点
        System.out.println("有度节点");
        TopologicalOrderIterator<String, DefaultEdge> toi = new TopologicalOrderIterator<>(graph);
        while (toi.hasNext()) {
            String vertex = toi.next();
            if (graph.inDegreeOf(vertex) > 0 || graph.outDegreeOf(vertex) > 0) {
                System.out.println(vertex);
            }
        }

        // 取 target 之后的所有节点
        System.out.println("取 target 之后的所有节点");
        String nodeName = "C";
        System.out.println(getTargetNodes(graph, nodeName));

    }

    public static <V, E> Set<V> getTargetNodes(Graph<V, E> graph, V sourceNode) {
        Set<V> targetNodes = new HashSet<>();

        // 获取从 sourceNode 出发的所有边
        Set<E> outgoingEdges = graph.outgoingEdgesOf(sourceNode);

        // 遍历边以获取目标节点
        for (E edge : outgoingEdges) {
            V target = graph.getEdgeTarget(edge);
            targetNodes.add(target);
            if (!graph.outgoingEdgesOf(target).isEmpty()) {
                targetNodes.addAll(getTargetNodes(graph, target));
            }
        }

        return targetNodes;
    }
}